/**
 *
 * @file
 *              petrov.cpp
 *
 * @brief
 *              Heap implementation by petrov
 */

/*TODO:
add correct sync. Remove redundant returns.
each synchronized function must have no more than 2 exits
don't forget about ReleaseMutex()!
*/

#include "heap_petrov.h"
#include <iostream>

heap_petrov::heap_petrov( size_t total, alloc_flags flag) : heap876(total, flag, "petrov"){  
	InitializeCriticalSection(&(this->cs));
	alloc_size = total;
	try{
		_heap = new char[total]; //throw bad alloc exception if no memory
	}
	catch(std::bad_alloc){
				std::cerr << "Can not allocate " << total << " bytes!";
				_heap = NULL;
	}
	M[_heap] = section(total, true, MM.insert(make_pair(total, _heap)));
}

heap_petrov::~heap_petrov(){
	free_all(0);
	DeleteCriticalSection(&cs);
};

void* heap_petrov::alloc( size_t sz, unsigned int tag ) {
	SyncHelper hp(cs);
	if(MM.empty())
		return 0;

	multimap<size_t, char*>::iterator itr = MM.find(sz);
	if(itr != MM.end()) {
		void* p = reinterpret_cast<void*>(itr->second);
		M[itr->second].is_empty = false;
		MM.erase(itr);
		return p;

	} else {
		itr = MM.upper_bound(sz);
		
		if(itr != MM.end()) {
			void* p = reinterpret_cast<void*>(itr->second);
			map<char*, section>::iterator temp_M1, temp_M2;
			pair<map<char*, section>::iterator, bool> pr;
			pr = M.insert(make_pair(itr->second + sz, section(itr->first - sz, true)));
			if(!pr.second)	return 0;	//FATAL ERROR
			temp_M1 = pr.first;

			temp_M2 = M.find(itr->second);
			temp_M2->second.is_empty = false;
			temp_M2->second.size = sz;
			temp_M2->second.itr = 0;
			
			temp_M1->second.itr = MM.insert(make_pair(M[itr->second + sz].size, itr->second + sz));
			MM.erase(itr);
			return p;
		}	
	}
	return 0;
}

void heap_petrov::free(void* ptr) {
	SyncHelper hp(cs);
	map<char*, section>::iterator itr = M.find((char*)ptr);

	if(itr == M.end())
		return;	//FATAL ERROR
	
	itr->second.is_empty = true;
	
	map<char*, section>::iterator temp_itr = itr;
	
	if(itr != M.begin()) {
		temp_itr--;
		if(temp_itr->second.is_empty) {
			MM.erase(temp_itr->second.itr);
			temp_itr->second.size += itr->second.size;
			M.erase(itr);
			itr = temp_itr;
		} else {
			temp_itr = itr;
		}
	}
	
	temp_itr++;
	if(temp_itr != M.end()) {
		if(temp_itr->second.is_empty) {
			MM.erase(temp_itr->second.itr);
			itr->second.size += temp_itr->second.size;
			M.erase(temp_itr);
		}
	}
	
	itr->second.itr = MM.insert(make_pair(itr->second.size, (char*)itr->first));
}

void heap_petrov::free_all(unsigned int tag) {
	SyncHelper hp(cs);
	MM.clear();
	M.clear();
	M[_heap] = section(alloc_size, true, MM.insert(make_pair(alloc_size, _heap)));
}

void heap_petrov::prt() {
	std::cout << "--------------------------" << std::endl;
	std::cout << "M (all sections)" << std::endl;
	map<char*, section>::iterator itr = M.begin();
	while(itr != M.end()) {
		std::cout << (int)itr->first << " " << itr->second.is_empty << " " << itr->second.size << std::endl;
		itr++;
	}

	std::cout << std::endl << "MM (free sections)" << std::endl;
	multimap<size_t, char*>::iterator itr1 = MM.begin();
	while(itr1 != MM.end()) {
		std::cout << itr1->first << " " << (int)itr1->second << std::endl;
		itr1++;
	}
	std::cout << std::endl;
}

/*
heap_petrov::heap_petrov( size_t total, alloc_flags flag):heap876(total, flag, "petrov"){        
        alloc_size = total;
        
        _heap = reinterpret_cast<void*>(new char[total]);
        push_list(_heap, total, true);
}


void heap_petrov::push_list(void* v, size_t s, bool b) {
        pair<size_t, bool> temp1;
        temp1.first = s;        temp1.second = b;
        pair<void*, pair<size_t, bool>> temp2;
        temp2.first = v;        temp2.second = temp1;
        mem_list.push_back(temp2);
}


void* heap_petrov::alloc( size_t sz, unsigned int tag ) {
        //vars
        //WaitForSingleObject(hMutex,INFINITE);


        list<pair<void*, pair<size_t, bool>>>::iterator itr = mem_list.begin();
        bool odd = true;
        size_t min = 0;
        if(sz % 2 == 0)
                odd = false;
        
        //find size of free space (min)
        while(itr != mem_list.end()) {
                if(itr->second.second && (itr->second.first >= sz)) {   //bool
                        if(itr->second.first == sz) {
                                min = sz;
                                break;
                        }
                        if(odd) {
                                if(itr->second.first % 2 == 1) {
                                        if(min) {
                                                min = min < itr->second.first?min:itr->second.first;
                                        } else {
                                                min = itr->second.first;
                                        }
                                }
                        } else {
                                if(min) {
                                        min = min < itr->second.first?min:itr->second.first;
                                } else {
                                        min = itr->second.first;
                                }
                        }
                }
                itr++;
        }
        
        //find iterator to free space
        itr = mem_list.begin();
        if(min) {
                while(itr != mem_list.end()) {
                        if(itr->second.second) {        //bool
                                if(itr->second.first == min)
                                        break;
                        }
                        itr++;
                }
        } else {
                while(itr != mem_list.end()) {
                        if(itr->second.second && (itr->second.first >= sz))
                                break;
                        itr++;
                }
        }
        
        //if need free space not exists
        if(itr == mem_list.end()){
                //ReleaseMutex(hMutex);
                return 0;
        }
        
        //alloc memory
        if(itr->second.first != sz)
                push_list(reinterpret_cast<void*>(reinterpret_cast<char*>(itr->first)+sz), itr->second.first-sz, true);
        itr->second.first = sz;
        itr->second.second = false;
        
        void* res = itr->first;
        mem_list.sort();


        //ReleaseMutex(hMutex);
        return res;
}
void heap_petrov::free( void* ptr ) {
        //WaitForSingleObject(hMutex,INFINITE);
        list<pair<void*, pair<size_t, bool>>>::iterator itr = mem_list.begin();
        while(itr != mem_list.end()) {
                if(itr->first == ptr) {
                        itr->second.second = true;
                        
                        //merge "free" records
                        list<pair<void*, pair<size_t, bool>>>::iterator curr_itr = itr;
                        bool flag_n = false;
                        bool flag_c = false;
                        if(itr != mem_list.begin()) {
                                itr--;
                                if(itr->second.second){
                                        itr->second.first+=curr_itr->second.first;
                                        flag_c = true;
                                }
                                itr++;
                        }
                        itr++;
                        if(itr != mem_list.end()) {
                                if(itr->second.second){
                                        if(flag_c){
                                                curr_itr--;
                                                curr_itr->second.first+=itr->second.first;
                                                flag_n = true;
                                                curr_itr++;
                                        } else {
                                                curr_itr->second.first+=itr->second.first;
                                                flag_n = true;
                                        }
                                }
                        }
                        
                        itr = curr_itr;
                        if(flag_c)
                                itr = mem_list.erase(itr);
                        else
                                itr++;


                        if(flag_n)
							mem_list.erase(itr);


                        break;
                }
                itr++;
        }
}


void heap_petrov::prt() {
        list<pair<void*, pair<size_t, bool>>>::iterator itr = mem_list.begin();
        while(itr != mem_list.end()) {
                std::cout << itr->first << " " << itr->second.first << " " << itr->second.second << std::endl;
                itr++;
        }
        std::cout << "------" << std::endl;
}


heap_petrov::~heap_petrov(){
        delete [] _heap;
}




void heap_petrov::free_all( unsigned int tag ){


        mem_list.clear();
        push_list(_heap, alloc_size, true);
        
}




size_t heap_petrov::get_occupancy() const { return alloc_size; }
*/